#include <iostream>

using namespace std;

// 函数结果状态代码
#define  TRUE 1  // 返回布尔值用于判断
#define  FALSE 0  // 同理
#define  OK 1  // 表示对表的操作成功
#define  ERROR 0  // 表示对表的操作失败
#define  INFEASIBLE -1  // 表示对表的操作不合理
#define  OVERFLOW -2  // 内存申请失败

// Status 是函数返回值类型，其值是函数结果状态代码
typedef int Status;  // using Status = int;

// 存储的数据类型
typedef int ElemType;

// 单链表的存储结构
typedef struct LNode {
    ElemType data;        // 数据域
    struct LNode *next;   // 指针域
}LNode, * LinkList;     

// 单链表的初始化
Status InitList_L (LinkList &L) { 
    L = new LNode;
    //生成 额外的结点（不用来存数据，不计入总长度） 作为头结点，用头指针 L 指向头结点            

    L->next = nullptr;   //头结点的指针域置空　

    return OK; 
} 

// 单链表的销毁
Status DestroyList_L (LinkList &L) {
    if (L) {    // 判断是否有空就需要释放，非空进入释放操作
        LinkList p = L;    // 先记录 需要释放的结点
        // 为了防止结点释放空间后
        // 结点中存放的 直接后继结点的地址 也被释放
        // 从而无法释放后继结点 
        // 我们用 额外的指针 来指向需要释放的结点
        // 在 单链表头指针 已经移动到 直接后继结点 后
        // 再释放 额外的指针 指向的结点

        while (L) {    // 只要单链表非空，就继续循环   
            L = L->next;    // 再移动 单链表头指针
            
            delete p;    // 最后释放 目标结点空间  

            p = L;    // 继续 记录 - 移动 - 释放
        }

        delete L;    // 不要忘记释放头结点
        
        return OK;
    } else {
        return INFEASIBLE;    // 空表无需释放，操作不合理
    }
}

// 单链表的判空
Status Is_Empty_L (LinkList L) { 
    // 表头不用来存储，所以从 首元结点 开始判断
    if (!L->next) {  
        return TRUE;    // 如果 首元结点 为空，单链表为空
    } else {
        return FALSE;    // 否则非空
    }
}

// 单链表的清空
Status ClearList_L (LinkList &L) {
    if (Is_Empty_L(L)) {
        return INFEASIBLE;    // 啥都没有还清
    }

    // 将 L 重置为空表 
    LinkList p = L-> next, q = p ->next;    // 已 记录 和 移动 
    // p 指向 首元结点，q 指向 p 的下一个
    // 清空需要保留头结点
    // 用 新的指针 来代替销毁操作中 头结点 的移动
    while (p) {    // 还有没释放的空间就继续释放
        // 已经 记录 和 移动，所以直接 释放 
        delete p;

        p = q;    // 与销毁操作同理，循环 记录 - 移动 - 释放 三步

        q = q->next;
    }

    L->next = nullptr;   // 头结点指针域置为空 

    return OK;
}

// 单链表的遍历
Status  TraverseList_L (LinkList &L) {
    if (Is_Empty_L(L)) {
        return INFEASIBLE;    // 空表
    }

    LinkList p = L->next;    // 从首元结点开始遍历

    while (p) {
        cout << p->data << " ";

        p = p->next;
    }

    cout << endl;
}

// 求单链表的表长
Status ListLength_L (LinkList L) {
    if (Is_Empty_L(L)) {
        return 0;    // 空表表长为 0
    }

    LinkList p = L->next;  // 从 首元结点 开始计数
     
    int sum = 0;

    //遍历单链表，统计结点数
    while (p) {   
        ++sum;
           
        p = p->next;    
    } 
    
    return sum;                             
}

// 获取单链表中某一个位置的元素，按位取值
Status GetElem_L (LinkList L, int i, ElemType &e) { 
    if (Is_Empty_L(L)) {
        return INFEASIBLE;    // 空表取值不合理
    }

    LinkList p = L->next;    // 依旧从 首元结点 开始
    
    int j = 1;    // 记录当前处在第几个位置
    
    // 当 p 的 直接后继 不为空 且 还未达到目标位置 时继续遍历
    while ( p && j < i) {
        p = p->next; 
       
        ++j; 
    }

    // !p 在 p 为空时进入 if语句
    // p 都为空退出 while 了，j 还没到达 i 的目标位置
    // 说明位置不合法，超出了单链表的当前长度
    // j > i 表示已经找过头了
    // 可是我们明明从 第一个位置 开始找的
    // 说明位置不合法，输入了小于 1 的位置
    if (!p || j > i) {    // 位置 偏大 或 偏小 都不合理
        return INFEASIBLE;    // 查找失败
    }

    e = p->data;    // 否则记录查找的值

    return OK;    // 查找成功 
}

// 查找单链表中某一个元素的地址，依值取址
LNode *LocateELem_L (LinkList L, ElemType e) {
    if (Is_Empty_L(L)) {
        return nullptr;    // 空表取址不合理
    }

    LinkList p = L->next;    // 依旧 首元
    
    // 当 直接后继非空 且 还未找到 时继续遍历
    while (p && p->data != e) {  
        p = p->next;
    }

    return p;    // 查找失败会返回 nullptr
} 

/*
// 获取单链表某一个元素的位置，依值取位
// 这算是 青春版？（狗头）
// 这里注释是因为 不允许有只有返回值类型不同的函数重载
Status LocateELem_L (LinkList L, ElemType e) {  
    if (Is_Empty_L(L)) {
        return INFEASIBLE;    // 空表取值不合理
    }

    LinkList p = L->next;    // 依旧从 首元结点 开始
    
    int j = 1;    // 记录当前处在第几个位置

    // 当 直接后继非空 且 还未找到 时继续遍历    
    while(p && p->data != e) {
        p=p->next;  

        ++j;
    }

    // 如果退出循环时非空，即 p->date 已经满足
    // 说明已经找到，可以返回计数器 j
    if (p) {
        return j;
    } else {
        return ERROR;    // 查找失败
    }
} 
*/

// 单链表的插入（在 L 中第 i 个元素之前插入数据元素 e）
Status ListInsert_L (LinkList &L, int i, ElemType e) {
    // 关键在于找到目标结点的前驱结点
    // 单链表不必判满
    // 注意，插入需要从 头结点 开始，而不是 首元结点
    // 因为可能插入到 第 1 个位置，此时首元结点改变
    LinkList p = L;

    int j = 0;    // 记录当前处在第几个位置

    // 当 p 的 直接后继 不为空 且 还未达到目标前驱结点 时继续遍历
    // 注意，是遍历至目标位置的前驱结点
    while (p && j < i - 1) {
        p = p->next;
        
        ++j;
    }
    
    // !p 在 p 为空时进入 if语句
    // p 都为空退出 while 了，j 还没到达 i 的前驱结点
    // 说明位置不合法，超出了单链表的当前长度 + 1
    // + 1 是因为 循环结束前又 ++j 了一次，但是插入允许尾插
    // j > i - 1 表示已经找过头了
    // 可是我们明明从，额，第 0 个位置 开始找的
    // 还能有比 0 更小的前驱？？？！！！
    // 说明位置不合法，输入了小于 1 的位置
    if(!p || j > i - 1) {    // 位置 偏大 或 偏小 都不合理
        return ERROR;    // 插入失败
    }

    // 如果 成功找到前驱 且 位置合理
    LNode* s = new LNode;    // 申请动态 新结点 s

    // 先存数据
    s->data = e;    // 将 待插入数据 e 存入 新结点 s 的数据域 
    // 如果先执行下面一步，目标前驱结点的指针域 就被 s 更新掉了
    s->next = p->next;	 // 让 新结点 s 的指针域指向 目标前驱结点的指针域
    // 等 p 发挥全部作用后再让 p（还记得 p 是我们找到的前驱吗） 的下一个指向 新结点 s
    // 目标位置的前驱的下一个指向新结点，说明新结点成功插入了  
    p->next = s;    //  让 目标前驱结点的指针域 指向 新节点 s 

    return OK; 
}

// 单链表的删除
Status ListDelete_L (LinkList &L, int i, ElemType &e) {
    // 关键在于找到目标结点的前驱结点
    // 单链表仍需判空
    if (Is_Empty_L(L)) {
        return INFEASIBLE;    // 空表删除不合理
    }

    // 注意，删除需要从 头结点 开始，而不是 首元结点
    // 因为可能删除 第 1 个位置，此时首元结点改变
    LinkList p = L;

    int j = 0;     // 记录当前处在第几个位置

    // 当 p 的 直接后继的直接后继 不为空 且 还未达到目标前驱结点 时继续遍历
    // 注意，是遍历至目标位置的前驱结点
    while( p->next && j < i - 1){               
        p = p->next; 
        
        ++j; 
    } 

    // !(p->next) 在 p->nxet 为空时进入 if语句
    // p-》next 都为空退出 while 了，j 还没到达 i 的前驱结点
    // 说明位置不合法，超出了单链表的当前长度，注意这里没有 + 1 了
    // 应为删除的位置不能超过表长，但插入可以插在表长 + 1 的位置
    // j > i - 1 表示已经找过头了
    // 可是我们明明从，额，第 0 个位置 开始找的
    // 还能有比 0 更小的前驱？？？！！！
    // 说明位置不合法，输入了小于 1 的位置
    if (!(p->next) || j > i - 1) {
        return ERROR;
    }

    // 如果 成功找到前驱 且 位置合理
    LNode *q = p->next;    // 先记录被删除结点的地址
    e = q->data;    // 保存 被删除结点的数据域，知道删了什么

    p->next = q->next;    // 让 目标前驱结点的指针域 指向 目标结点的指针域

    delete q;     // 释放被删除结点的动态空间以防止内存泄漏 

    return OK; 
}